//#include<iostream>
#include "GenericPermutation.h"

template<typename T, typename container>
GenericPermutation<T,container>::GenericPermutation(container& elementContainer){
    initialize(elementContainer, elementContainer.size());
}

template<typename T, typename container>
GenericPermutation<T,container>::GenericPermutation(container& elementContainer, int n){
    initialize(elementContainer, n);
}


template<typename T, typename container>
void GenericPermutation<T,container>::initialize(container& elementContainer, int n){
     elementCont = new std::map<T,int>();
     permutationNumber = n;
     //Count the elements using a map container
     for(typename container::iterator it = elementContainer.begin(); it != elementContainer.end(); it++){
            (*elementCont)[*it]++;      
     }
}

template<typename T, typename container>
GenericPermutation<T,container>::~GenericPermutation(){
     delete elementCont;
}

template<typename T, typename container>
typename GenericPermutation<T,container>::iterator
GenericPermutation<T,container>::begin(){
     typename GenericPermutation<T,container>::iterator it(*this,(*this).permutationNumber);
     return it;
}

template<typename T, typename container>
typename GenericPermutation<T,container>::iterator
GenericPermutation<T,container>::end(){
     typename GenericPermutation<T,container>::iterator it(*this,(*this).permutationNumber,true);
     return it;
}
//=============================================================================================
//==================Iterator Implementation====================================================
//=============================================================================================

//Iterator constructor
template<typename T, typename container>
GenericPermutation<T,container>::iterator::iterator(
                           GenericPermutation<T,container>& gPc, int n, bool iAE) : elementSet(gPc){
           //elementSet = gPc;
           permutationNumber = n;
           stc = 0;//new std::stack<typename std::map<T,int>::iterator>();
           isAfterEnd = iAE;
           if(!iAE){
                    reset();
           }     
}
//Iterator copy constructor
template<typename T, typename container>
GenericPermutation<T,container>::iterator::iterator(const
                           typename GenericPermutation<T,container>::iterator& right ) : elementSet(right.elementSet){
           elementSet = right.elementSet;  //warning: working with references
           permutationNumber = right.permutationNumber;
           state = right.state;
           //stc must be copied
           stc = new std::stack<typename std::map<T,int>::iterator>(*right.stc);
           count = right.count;
           isBeforeStart = right.isBeforeStart;
           isAfterEnd = right.isAfterEnd;
}
//Iterator Destructor
template<typename T, typename container>
GenericPermutation<T,container>::iterator::~iterator(){
            delete stc;
}
//Reset function
template<typename T, typename container>
void GenericPermutation<T,container>::iterator::reset(){
     isAfterEnd = false;
     isBeforeStart = true;
     if(stc) delete stc;  //Delete stc
     //Create an empty stack
     stc = new std::stack<typename std::map<T,int>::iterator>();
     typename std::map<T,int>::iterator iter = elementSet.elementCont->begin();
     stc->push(iter);
     count = 0;
     increment();
     /*It is, at this point, introduce a registration mechanism in order to
      *use the correct function to insert an element in the last position
      */
     //state.push_back(); The state is empty at the start point, it is the best way 
}
//Increment function
template<typename T, typename container>
bool GenericPermutation<T,container>::iterator::increment(){
     if(isAfterEnd) return false;
   
    typename std::map<T,int>::iterator tempIter;
    //We should use a registration interface to call the correct function in this place
    if(!state.empty()) state.pop_back();  //pop
    //typename container::iterator it = state.end();
    //if(!state.empty()) state.erase(--it);
    int num;
    while(count != permutationNumber){
                tempIter = stc->top();
                //stc->pop();
                if(tempIter != elementSet.elementCont->end()){
                            num = 0;
                            for(int i=0; i<count; i++)
                                if(state[i]==(stc->top())->first) num++;
                            if(num<(*(elementSet.elementCont))[stc->top()->first]){
                                        state.push_back(stc->top()->first);  //push
                                        //it = state.end();
                                        //state.insert(it,1,stc->top()->first);
                                        count++;
                                        tempIter++;
                                        stc->pop();
                                        stc->push(tempIter);
                                        tempIter = elementSet.elementCont->begin();
                                        stc->push(tempIter);
                            }
                            else{
                                tempIter++;
                                stc->pop();
                                stc->push(tempIter);
                            }
                }
                else{
                     if(!state.empty()) state.pop_back();  //pop
                     /*if(!state.empty()){
                         it = --state.end();
                         state.erase(it);
                     }*/
                     stc->pop();
                     count--;
                     if(count<0){
                                 this->isAfterEnd = true;
                                 return false;
                     }
                }
    }
    stc->pop();
    count--;
    if(count<0) this->isAfterEnd = true;
    return true;
}
//------------
//Operators overloading
template<typename T, typename container>
container GenericPermutation<T,container>::iterator::operator*(){
           return state;
}  //operator*
template<typename T, typename container>
typename GenericPermutation<T,container>::iterator
         GenericPermutation<T,container>::iterator::operator++(){
    increment();
    return *this;
}  //operator++
template<typename T, typename container>
bool GenericPermutation<T,container>::iterator::operator==(const typename GenericPermutation<T,container>::iterator& it){
     if(isAfterEnd) return isAfterEnd == it.isAfterEnd;
     if(isBeforeStart) return isBeforeStart == it.isBeforeStart;
     //For now, two iterators to the middle are always different
     return false;
}  //operator==
template<typename T, typename container>
bool GenericPermutation<T,container>::iterator::operator!=(const typename GenericPermutation<T,container>::iterator& it){
     return !((*this)==it);
}  //operator!=
template<typename T, typename container>
typename GenericPermutation<T,container>::iterator&
GenericPermutation<T,container>::iterator::operator=(const typename GenericPermutation<T,container>::iterator& it){
    iterator iter(it);
    return iter;
}  //operator=
